package tree;

/**
 *
 */

public class Solution222 {
    int maxLevel = -1;
    int nodesInMaxLevel = 0;

    public static void main(String[] args) {
        System.out.println(new Solution222().countNodes(genRoot3()));

    }


    private static TreeNode genRoot1() {
        TreeNode level3_1 = new TreeNode(4);
        TreeNode level3_2 = new TreeNode(5);
        TreeNode level3_3 = new TreeNode(6);
        TreeNode level3_4 = new TreeNode(7);

        TreeNode level2_1 = new TreeNode(2);
        TreeNode level2_2 = new TreeNode(3);

        TreeNode root = new TreeNode(1);

        level2_1.left = level3_1;
        level2_1.right = level3_2;

        level2_2.left = level3_3;
        level2_2.right = level3_4;

        root.left = level2_1;
        root.right = level2_2;

        return root;
    }


    private static TreeNode genRoot2() {
        TreeNode level3_1 = new TreeNode(4);
        TreeNode level3_2 = new TreeNode(5);

        TreeNode level2_1 = new TreeNode(2);
        TreeNode level2_2 = new TreeNode(3);

        TreeNode root = new TreeNode(1);

        level2_1.left = level3_1;
        level2_1.right = level3_2;

        root.left = level2_1;
        root.right = level2_2;

        return root;
    }

    private static TreeNode genRoot3() {
        TreeNode level3_1 = new TreeNode(4);

        TreeNode level2_1 = new TreeNode(2);
        TreeNode level2_2 = new TreeNode(3);

        TreeNode root = new TreeNode(1);

        level2_1.left = level3_1;

        root.left = level2_1;
        root.right = level2_2;

        return root;
    }


    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        maxLevel = getMaxLevel(root, 1);
        check(root.left, root.right, maxLevel, 1);

        return (int) Math.pow(2, maxLevel - 1) - 1 + nodesInMaxLevel;
    }

    private int getMaxLevel(TreeNode root, int initLevel) {
        while (root.left != null) {
            root = root.left;

            initLevel++;
        }

        return initLevel;
    }

    public void check(TreeNode left, TreeNode right, int maxLevel, int parentLevel) {
        if (left == null && right == null) {
            nodesInMaxLevel += 1;
            return;
        }

        if (left != null && right == null) {
            check(left.left, left.right, maxLevel, parentLevel + 1);
            return;
        }


        if (left != null && right != null) {
            int rightMaxLevel = getMaxLevel(right, parentLevel + 1);

            // right lower, checkLeft
            if (rightMaxLevel < maxLevel) {
                check(left.left, left.right, maxLevel, parentLevel + 1);
            } else {
                // right equals, + part
                nodesInMaxLevel += (int) Math.pow(2, maxLevel - 1 - parentLevel);
                check(right.left, right.right, maxLevel, parentLevel + 1);
            }
        }
    }

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return "val: " + val;
        }
    }
}
